package offer.day31;

public class No51InversePairs {
    /*
     * 面试题51：数组中的逆序对
     * 题目：在数组中的两个数字，如果前面的数字大于后面的数字，则这两个数字组成一个逆序对。
     * 输入一个数组，求出数组中的逆序对总数
     * 例如：在数组{7，5，6，4}中，一共存在5个逆序对，分别是{7，5}{7，6}{7，4}{5，4}{6，4}
     *
     * 思路：统计逆序对
     * 1> 将数组分割成子数组，再将子数组进行分割 ，直到分割为长度为1的数组
     * 2> 统计子数组中最短的数组（两两进行合并）之间的逆序对的数目，然后再统计相邻的子数组中的逆序对的数目，直到合并为一个整体之后
     * 其中，在2>中进行统计逆序对的数目时，需要构建一个辅助数组，将两个数组合并后的新数组存入，构建两个索引，都从最后一个开始
     * 比较两个指针指向的值，
     * （1）若第一个数组中的值大于第二个数组中的值，则逆序对的数目等于第二个数组中前面还剩余元素个数，
     * 		并将较大的数存入辅助数组，然后将较大数所在的数组的指针和辅助数组的指针向前移动
     * （2）若第一个数组的值小于等于第二个数组中的值，则无逆序对
     * 		并将较大的数存入辅助数组，然后将较大数所在的数组的指针和辅助数组的指针向前移动
     *
     * 时间复杂度O(nlogn)   空间复杂度O(n)    以空间换时间的算法
     *
     * 其实现过程实际上就是2-路归并排序的过程：
     * 归并：将两个或两个以上的有序表组合成一个新的有序表
     *
     * 初始序列含有n个记录，则可以看成时有n个子序列，每个子序列的长度为1，然后进行两两合并，得到n/2(取整)个长度为2或者1的有序子序列。
     * 然后再进行两两合并，。。。，直到得到一个长度为n的有序序列为止
     *
     * */
    public static void main(String[] args) {
        No51InversePairs p = new No51InversePairs();
        int[] array = {7,5,6,4};//其中array{0] = 7
        System.out.println("数组中逆序对一共有："+p.InversePairs(array));
    }

    int count=0;
    private int InversePairs(int[] array) {
        if(array==null||array.length==0) return 0;
        mergeSort(array,0,array.length-1);
        return count;
    }

    private void mergeSort(int[] array, int start, int end) {
        int mid=(start+end)/2;
        if(start<end){
            mergeSort(array,start,mid);
            mergeSort(array,mid+1,end);
            merge(array,start,mid,end);
        }
    }

    private void merge(int[] array, int start, int mid, int end) {
        int[] help=new int[end-start+1];

        int p1=mid;
        int p2=end;
        int p3=end-start;

        while(p1>=start && p2>=mid+1){
            if(array[p1]>array[p2]){
                count+=(p2-mid);
                help[p3--]=array[p1--];
            }else{
                help[p3--]=array[p2--];
            }
        }
        while(p1>=start){
            help[p3--]=array[p1--];
        }
        while(p2>=mid+1){
            help[p3--]=array[p2--];
        }
        for(int i=0;i<help.length;i++){
            array[start++]=help[i];
        }
    }
}
